package algorithms.heap;

import algorithms.tree.BinaryNode;
import algorithms.tree.BinaryTree;

public class SkewHeap extends BinaryTree<Integer> {

	public void merge(BinaryNode<Integer> node) {
		if (this.rootNode == null) {
			this.rootNode = node;
		} else {
			this.rootNode = merge0(this.rootNode, node);
		}
	}

	public BinaryNode<Integer> pop() {
		BinaryNode<Integer> node = this.rootNode;
		if (node == null) {
			return null;
		}
		BinaryNode<Integer> left = rootNode.getLeft();
		BinaryNode<Integer> right = rootNode.getRight();
		if (left != null && right != null) {
			this.rootNode = merge0(left, right);
		} else if (right == null && left != null) {
			rootNode = left;
		} else if (right != null && left == null) {
			rootNode = right;
		} else {
			rootNode = null;
		}
		return node;
	}

	/**
	 * 和左偏堆基本一致，只是合并后强制交换左右子树，以此来提高树的平衡
	 * 
	 * @param l
	 * @param r
	 * @return
	 */
	private BinaryNode<Integer> merge0(BinaryNode<Integer> l, BinaryNode<Integer> r) {
		if (l == null) {
			return r;
		}
		if (r == null) {
			return l;
		}
		if (r.getKey() < l.getKey()) {
			r.setRight(merge0(l, r.getRight()));
			exchange(r);
			return r;
		} else {
			l.setRight(merge0(r, l.getRight()));
			exchange(l);
			return l;
		}
	}

	private void exchange(BinaryNode<Integer> node) {
		BinaryNode<Integer> tmp = node.getLeft();
		node.setLeft(node.getRight());
		node.setRight(tmp);
	}
}
